package day04;

import java.util.PriorityQueue;
import java.util.Queue;

public class 数组中的第K个最大元素 {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 建立一个大根堆
        buildMAXHeap(nums, n);
        // 取出第k大元素
        for (int i = n - 1; i >= n - k; i--) {
            // 将堆顶元素（当前最大值）与最后一个元素交换
            swap(nums, 0, i);
            // 调整堆，使其重新满足大根堆的性质
            siftDown(nums, 0, i);
        }
        // 返回第k大元素
        return nums[n - k];
    }

    // 手动建立大根堆，基于数组
    public void buildMAXHeap(int[] nums, int n) {
        // 从最后一个非叶子节点开始，依次向上调整
        for (int parent = (n - 1) / 2; parent >= 0; parent--) {
            siftDown(nums, parent, n);
        }
    }

    private void siftDown(int[] nums, int parent, int end) {
        int child = 2 * parent + 1; // 左孩子
        while (child < end) {
            // 如果右孩子存在且比左孩子大，选择右孩子
            if (child + 1 < end && nums[child] < nums[child + 1]) {
                child++;
            }
            // 如果孩子比父节点大，交换并继续向下调整
            if (nums[child] > nums[parent]) {
                swap(nums, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
//    public int findKthLargest(int[] nums, int k) {
//        int n = nums.length;
//        // 创建一个最小堆（默认就是最小堆）
//        PriorityQueue<Integer> q = new PriorityQueue<>();
//        // 利用循环向最小堆里面添加元素
//        for(int x : nums){
//            q.offer(x);
//            // 进行判断
//            if(q.size() > k){
//                q.poll();
//            }
//        }
//        return q.peek();
//    }
}
